%begin%
\documentclass[11pt]{article}
\usepackage{array,calc,fancyhdr,lastpage}
\usepackage[hmargin=.5in,vmargin=.75in,
            footskip=.25in,headsep=.5in-\headheight]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{tikz}

% Page layout: stretch text to fill up page.
\flushbottom

% Common formatting macros for CSC165.
\input{macros-165}

% Headings.
\pagestyle{fancy}
\let\headrule\empty
\let\footrule\empty
\lhead{{CSC\,165\,H1F}}
\chead{{\scshape Homework Exercise \#\,4 --- Sample Solutions}}
\rhead{{Fall 2013}}
\lfoot{{Dept.\ of Computer Science,
    University of Toronto, St.~George Campus}}
\cfoot{{}}
\rfoot{{Page \thepage\ of \pageref{LastPage}}}


\begin{document}

\noindent
\rule{\textwidth}{.5pt}

\subsection*{Topic: Tautologies and derivations.}

\begin{enumerate}
%
% Q1
%
\item
Show (perhaps by using a truth table) that 
\begin{enumerate}
  \item $[(P \implies Q) \land P] \implies Q$ is a tautology. 
        (This rule is called {\em modus ponens}.) \\
  \begin{bf}
    Taking the truth table approach, we have:
    $$\begin{array}{c|c|c|c|c}
       P & Q & P \implies Q & (P \implies Q) \land P 
            & [(P \implies Q) \land P] \implies Q \\
       \hline
       T & T & T & T & T \\
       T & F & F & F & T \\
       F & T & T & F & T \\
       F & F & T & F & T 
      \end{array}$$
    The last column shows us that $[(P \implies Q) \land P] \implies Q$
    is true independent of the definition of $P$ and $Q$, and therefore 
    the statement is a tautology.  This could also be done by showing that
    the statement is equivalent to $R \lor \lnot R$ for any $R.$
  \end{bf}
  \item $[(P \implies Q) \land Q] \implies P$ is not a tautology.
        (This fallacy is called {\em The fallacy of affirming the consequent}.) \\
  \begin{bf}
    We have:
    $$\begin{array}{c|c|c|c|c}
       P & Q & P \implies Q & (P \implies Q) \land Q 
            & [(P \implies Q) \land Q] \implies P \\
       \hline
       T & T & T & T & T \\
       T & F & F & F & T \\
       F & T & T & T & F \\
       F & F & T & F & T 
      \end{array}$$
    We see from the last column that $[(P \implies Q) \land Q] \implies P$
    is false when $P$ is false and $Q$ is true.  Hence the statement is not
    a tautology.   (Note this can be done in one-line if you can deduce which
    values for $P$ and $Q$ make the statement false without building the 
    whole table.)
  \end{bf}
  \item $[(P \implies Q) \land \lnot P] \implies \lnot Q$ is not a tautology.
        (This fallacy is called {\em The fallacy of denying the antecedent}.) \\
  \begin{bf}
    We have:
    $$\begin{array}{c|c|c|c|c|c|c}
       P & Q & P \implies Q & \lnot P & (P \implies Q) \land \lnot P &\lnot Q 
            & [(P \implies Q) \land \lnot P] \implies \lnot Q \\
       \hline
       T & T & T & F & F & F & T \\
       T & F & F & F & F & T & T \\
       F & T & T & T & T & F & F \\
       F & F & T & T & T & T & T 
      \end{array}$$
    We see from the last column that 
    $[(P \implies Q) \land \lnot P] \implies \lnot Q$
    is false when $P$ is false and $Q$ is true.  Hence the statement is not
    a tautology.   (Note this can be done in one-line if you can deduce which
    values for $P$ and $Q$ make the statement false without building the 
    whole table.)
  \end{bf}
  \item $[(P \implies Q) \land \lnot Q] \implies \lnot P$ is a tautology. 
        (This rule is called {\em modus tollens}.) \\
  \begin{bf}
    We have:
    $$\begin{array}{c|c|c|c|c|c|c}
       P & Q & P \implies Q & \lnot Q & (P \implies Q) \land \lnot Q &\lnot P 
            & [(P \implies Q) \land \lnot Q] \implies \lnot P \\
       \hline
       T & T & T & F & F & F & T \\
       T & F & F & T & F & F & T \\
       F & T & T & F & F & T & T \\
       F & F & T & T & T & T & T 
      \end{array}$$
    The last column shows us that 
    $[(P \implies Q) \land \lnot Q] \implies \lnot P$
    is true independent of the definition of $P$ and $Q$, and therefore 
    the statement is a tautology.  This could also be done by showing that
    the statement is equivalent to $R \lor \lnot R$ for any $R.$
  \end{bf}
\end{enumerate}
%
% Q2
%
\item
Show that $P \land ( Q \implies R )$ and $(P \land Q) \implies (P \land R)$
are {\bf not} logically equivalent.  (This means that $\land$ does not 
distribute over $\implies$.)\\
  \begin{bf}
    One could start by observing that if $P$ is false, 
    $P \land ( Q \implies R )$ is false, 
    while $(P \land Q) \implies (P \land R)$ is true, because the 
    antecendent is false.  This is independent of the values of $Q$ and $R$.
    Hence the two statements are not equivalent, and $\land$ does not
    distribute over $\implies$.

    Taking the brute-force truth table approach, we have:
    $$\begin{array}{c|c|c|c|c|c|c|c}
       P & Q & R & Q \implies R & P \land (Q \implies R) 
            & P \land Q & P \land R & (P \land Q) \implies (P \land R) \\
       \hline
       T & T & T & T & T & T & T & T \\
       T & T & F & F & F & T & F & F \\
       T & F & T & T & T & F & T & T \\
       T & F & F & T & T & F & F & T \\
       F & T & T & T & F & F & F & T \\
       F & T & F & F & F & F & F & T \\
       F & F & T & T & F & F & F & T \\  
       F & F & F & T & F & F & F & T   
      \end{array}$$
      Since the fifth and last columns differ, we can conclude that the
      given expressions are not equivalent.
    \end{bf}
%
% Q3
%
\item
\begin{enumerate}
  \item 
    Give a derivation to show that
    $[ P \implies (Q \implies R)]$
    is equivalent to  $[(P \land Q) \implies R]$.
    Justify each step of your derivation.
    Do not use truth tables or Venn diagrams.\\
    \begin{bf}
        $$\begin{array}{cll}
           ~ & [ P \implies (Q \implies R)] & \\
           \lequiv & [ P \implies (\lnot Q \lor R)] & \mbox{(implication rule)}\\
           \lequiv & [ \lnot P \lor (\lnot Q \lor R)] & \mbox{(implication rule)}\\
           \lequiv & [ (\lnot P \lor \lnot Q) \lor R] & \mbox{(associativity rule)}\\
           \lequiv & [ \lnot (P \land Q) \lor R] & \mbox{(a de Morgan rule)}\\
           \lequiv & [ (P \land Q) \implies R] & \mbox{(implication rule)}
          \end{array}$$
        We can conclude that $[ P \implies (Q \implies R)]$
        is equivalent to  $[(P \land Q) \implies R]$.
    \end{bf}
  \item 
Give a derivation to show that
$\lnot ( P \iff Q )$
is equivalent to  $[(P \land \lnot Q) \lor (\lnot P \land Q)]$.
Justify each step of your derivation.
Do not use truth tables or Venn diagrams.\\
    \begin{bf}
        $$\begin{array}{rcll}
           \lnot ( P \iff Q ) 
             & \lequiv & \lnot [ (P \land Q) \lor (\lnot P \land \lnot Q) ]  
               & \mbox{(derived in lecture)}\\
           ~ & \lequiv & \lnot (P \land Q) \land \lnot (\lnot P \land \lnot Q)  
               & \mbox{(a de Morgan rule)}\\
           ~ & \lequiv & (\lnot P \lor \lnot Q) \land (\lnot \lnot P \lor \lnot \lnot Q)  
               & \mbox{(a de Morgan rule)}\\
           ~ & \lequiv & (\lnot P \lor \lnot Q) \land (P \lor Q)  
               & \mbox{(double negation)}\\
           ~ & \lequiv & ((\lnot P \lor \lnot Q) \land P)  \lor
                         ((\lnot P \lor \lnot Q) \land Q)  
               & \mbox{(distributivity)}\\
           ~ & \lequiv & ((\lnot P \land P) \lor (\lnot Q \land P))  \lor
                         ((\lnot P \land Q) \lor (\lnot Q \land Q)) 
               & \mbox{(distributivity)}\\
           ~ & \lequiv & (\lnot Q \land P)  \lor
                         (\lnot P \land Q)
               & \mbox{(identity)}\\
           ~ & \lequiv & (P \land \lnot Q)  \lor
                         (\lnot P \land Q)
               & \mbox{(commutivity)}\\
          \end{array}$$
        We can conclude that $\lnot ( P \iff Q )$
        is equivalent to  $[(P \land \lnot Q) \lor (\lnot P \land Q)]$.
    \end{bf}
\end{enumerate}
%
% Q4
%
\item
There are many social clubs on campus that you can join. One such club,
called the Truth-tellers club, has members who only make statements
that are true.  Another club, called the Falsehood-tellers club,
has members who only make statements that are false.  Clearly,
no one can be a member of both clubs.

Students Paul, Michelle and Tom are each club members.
They make the following statements:

\begin{tabular}{crl}
  \qquad & {\bf Paul:} &  Michelle and Tom belong to different clubs.\\
  \qquad & {\bf Michelle:} & Paul is a Truth-teller.\\
  \qquad & {\bf Tom:} &  Paul is a Falsehood-teller.
\end{tabular}

Which of these three students is a Truth-teller?  Justify your answer. \\

  \begin{bf}
      There are many ways to solve this problem.  If we start by analyzing
      the statements of Michelle and Tom, we see that they each say the 
      opposite of the other.  Hence, one of them is telling the truth and
      one of them is not telling the truth.  This means that they must
      belong to different clubs.  But this is what Paul said.  Paul is telling
      the truth.  And so Paul
      must belong to the Truth-tellers club.  But that is what Michelle said!
      Michelle is telling the truth. 
      And so Michelle must also belong to the Truth-tellers club.  Tom said
      that Paul is a Falsehood-teller, which we know is a lie.  And so Tom
      must be in the Falsehood-tellers club.

      In summary, Paul and Michelle are members of the Truth-tellers
      club, and Tom is a member of the Falsehood-tellers club.
  \end{bf}

\end{enumerate}
\noindent
If you have questions or 
encounter any difficulties, post a description of the issue on the course
forum. 
\end{document}
